/******************************************
Arbol_huffman.java
Universidad del Valle de Guatemala
Algoritmos y Estructura de Datos
Autor:
    Martín Guzmán
Fecha: 30 de septiembre de 2009
Descripción: Contiene la descripción de un
 * árbol de huffman. En esta clase se genera
 * el árbol y se busca el código de determinado
 * carácter
*******************************************/
import java.util.LinkedList;
import java.lang.reflect.Array;
import java.lang.AssertionError;

public class Arbol_2_3<G> implements Interfaz_Arbol_2_3<G>{

    Nodo<String> padre_der;
    Nodo<String> padre_izq;
    private LinkedList<G> lista;
    
    //método constructor
    public Arbol_2_3(LinkedList<G> lista){

        padre_der = new Nodo("");
        padre_izq = new Nodo("");

        this.lista= new LinkedList<G>();
        
        //copiar la lista sin hacer aliaces
        for(int i=0;i<lista.size();i++){
            this.lista.add(lista.get(i));
        }

    }

    //método para generar el arbol de 2-3
    public Nodo<String> Generar_arbol(LinkedList<G> lista){

        Nodo<String> nodo = new Nodo<String>("");
        LinkedList<G> lista_temporal = new LinkedList<G>();

        //copiar la sublista
        for(int i=0;i<lista.size();i++){
            lista_temporal.add(lista.get(i));
        }

        //********************
        //System.out.println("\nTamaño de la lista: "+lista_temporal.size());

        /*
        for(int i=0;i<this.lista.size();i++){
            System.out.println("elemento i: "+this.lista.get(i));
        }
        */

        //**********************************************************************
        // para cortar el arreglo en 2
        //System.out.println(Sorting.es_par((LinkedList<Object>)lista_temporal));
        int indice_a_cortar=0;
        if(Sorting.es_par((LinkedList<Object>)lista_temporal)==true){//es par
            indice_a_cortar=lista_temporal.size()/2-1;
        }
        else{
            indice_a_cortar=lista_temporal.size()/2;
        }
        //**********************************************************************

        //System.out.println("Cortar en: "+indice_a_cortar);

        if(lista_temporal.size()==0){
            //System.out.println("rama con una hoja");
            nodo.setNombre("");
            return nodo;
        }
        if(lista_temporal.size()==1){
            //System.out.println("rama con una hoja");
            nodo.setNombre(""+lista_temporal.get(0).toString());
            return nodo;
        }
        if(lista_temporal.size()==2){
            //System.out.println("rama con dos hojas");
            nodo.setNombre(""+lista_temporal.get(0).toString()+","+lista_temporal.get(1).toString());
            return nodo;
        }

        LinkedList<G> sub_der = new LinkedList<G>();
        for(int i=0;i<indice_a_cortar;i++){
            sub_der.add(lista_temporal.get(i));
            //System.out.println("Lista derecha: "+lista_temporal.get(i));
        }

        Nodo<String> nodo_padresco = new Nodo<String>(""+lista_temporal.get(indice_a_cortar));
        //System.out.println("Nodo: "+lista_temporal.get(indice_a_cortar));
        
        LinkedList<G> sub_izq = new LinkedList<G>();
        for(int i=indice_a_cortar+1;i<lista_temporal.size();i++){
            sub_izq.add(lista_temporal.get(i));
            //System.out.println("Lista izquierda: "+lista_temporal.get(i));
        }

        //System.out.println("Toca el hijo der");
        nodo_padresco.setHijo_derecho(Generar_arbol(sub_der));
        //System.out.println("Toca el hijo izq");
        nodo_padresco.setHijo_izquierdo(Generar_arbol(sub_izq));
        
        return nodo_padresco;
    }

    public void Insertar(G A_Insertar) {
        getLista().add(A_Insertar);
        Generar_arbol(getLista());
    }

    public void Retirar(G A_Quitar) {
        getLista().remove(A_Quitar);
        Generar_arbol(getLista());
    }

    public String Mostrar() {
        String temp = padre_der.Mostrar_Nodo()+",";
        temp+= padre_izq.Mostrar_Nodo();
        return "";
    }

    public G Buscar(G Elemento) {
        if(getLista().indexOf(Elemento)==-1)
            return null;
        return Elemento;
    }

    public LinkedList<G> getLista() {
        return lista;
    }

    public void setLista(LinkedList<G> lista) {
        this.lista = lista;
    }


}